//给你二叉树的根结点 root ，请你将它展开为一个单链表： 
//
// 
// 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 
// 展开后的单链表应该与二叉树 先序遍历 顺序相同。 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [1,2,5,3,4,null,6]
//输出：[1,null,2,null,3,null,4,null,5,null,6]
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 树中结点数在范围 [0, 2000] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ 
//
// Related Topics 栈 树 深度优先搜索 链表 二叉树 👍 1600 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class FlattenBinaryTreeToLinkedList {
    public static void main(String[] args) {
        Solution solution = new FlattenBinaryTreeToLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        /**
         * 直接先序遍历的结果存到list当中，然后循环处理这个list
         *
         * @param root
         */
//    public void flatten(TreeNode root) {
//        if (root == null) return ;
//        List<TreeNode> list = new ArrayList<>();
//        readNode(root,list);
//        TreeNode pre = new TreeNode(-1  );
//        TreeNode curr = pre;
//        for (TreeNode treeNode : list) {
//            curr.left = null;
//            curr.right = treeNode;
//            curr = curr.right;
//        }
//    }
//
//    private void readNode(TreeNode root, List<TreeNode> list) {
//        if (root == null) return;
//        list.add(root);
//        readNode(root.left,list);
//        readNode(root.right,list);
//    }

        /**
         * 把当前节点的右子树放到左子树最右侧变成一条右路连表，可以看一下官方题解第三种方法的动图
         * @param root
         */
        public void flatten(TreeNode root) {
            if (root == null) return;
            TreeNode curr = root;
            while (curr != null) {
                //如果存在左子树 当前节点的右子树放到左子树最右侧
                if (curr.left!=null){
                    //寻找最右节点
                    TreeNode p1 = curr.left;
                    TreeNode p2 = p1;
                    while (p2.right!=null){
                        p2 = p2.right;
                    }
                    //当前节点的右子树挂  到左子树最右侧
                    p2.right = curr.right;
                    //当前节点左子树移动到右子节点，左子节点清空
                    curr.right = curr.left;
                    curr.left = null;
                }
                curr = curr.right;
            }
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}